import java.util.HashSet;
import java.util.List;
import java.util.Set;

//不同的二叉搜索树
class Solution {
    public int numTrees(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }

        }

        return dp[n];
    }
}



//回文字串的个数

class Solution1 {
    public int countSubstrings(String s) {
        char[] arr=s.toCharArray();

        int n=arr.length;
        int ret=0;
        boolean[][] dp=new boolean[n][n];
        for(int i=n;i>=0;i--){
            for(int j=i;j<n;j++){
                if(arr[i]!=arr[j]) dp[i][j]=false;
                else dp[i][j]=(i+1==j||i==j)?true:dp[i+1][j-1];

                if(dp[i][j]) ret++;


            }
        }

        return ret;

    }


    private boolean is(int left,int right,char[] arr){
        while(left<right){
            if(arr[left++]!=arr[right--]) return false;
        }

        return true;

    }
}


//最长会问字串
class Solution2 {
    public String longestPalindrome(String s) {
        char[] arr=s.toCharArray();
        int n=arr.length;
        int[] ret=new int[2];
        int len=0;
        boolean[][] dp=new boolean[n][n];
        for(int i=n;i>=0;i--){
            for(int j=i;j<n;j++){
                if(arr[i]!=arr[j]) dp[i][j]=false;
                else dp[i][j]=(i+1==j||i==j)?true:dp[i+1][j-1];

                if(dp[i][j]&&j-i>len){
                    len=j-i;
                    ret[0]=i;
                    ret[1]=j;
                }


            }
        }


        return s.substring(ret[0],ret[1]+1);
    }
}



//是否能分成三段回文字串
class Solution4 {
    public boolean checkPartitioning(String s) {
        char[] arr=s.toCharArray();

        int n=arr.length;
        int ret=0;
        boolean[][] dp=new boolean[n][n];
        for(int i=n;i>=0;i--){
            for(int j=i;j<n;j++){
                if(arr[i]!=arr[j]) dp[i][j]=false;
                else dp[i][j]=(i+1==j||i==j)?true:dp[i+1][j-1];
            }
        }

        for(int i=1;i<n-1;i++){
            for(int j=i;j<n-1;j++)
                if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;

        }
        return false;
    }
}



//最小切割数，使每段都是回文子串
class Solution5 {
    public int minCut(String s) {
        char[] arr=s.toCharArray();

        int n=arr.length;
        int ret=0;
        boolean[][] dp=new boolean[n][n];
        int[] dp1=new int[n];
        for(int i=n;i>=0;i--){
            for(int j=i;j<n;j++){
                if(arr[i]==arr[j])  dp[i][j]=(i+1==j||i==j)?true:dp[i+1][j-1];
            }
        }

        if(dp[0][n-1]) return 0;

        for(int i=1;i<n;i++){
            if(dp[0][i]){
                dp1[i]=0;
                continue;
            }
            for(int j=1;j<=i;j++){
                if(dp[j][i]){
                    if(dp1[i]==0) dp1[i]=dp1[j-1]+1;
                    else dp1[i]=Math.min(dp1[j-1]+1,dp1[i]);

                }

            }
        }
        return dp1[n-1];
    }
}


//最长回文子串
class Solution6 {
    public int longestPalindromeSubseq(String s) {
        char[] arr=s.toCharArray();
        int n=arr.length;
        int[][] dp=new int[n][n];

        for(int i=n-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i+1;j<n;j++){
                if(arr[i]==arr[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }

        return dp[0][n-1];
    }
}


//最小插入次数使字符串为回文串
class Solution7 {
    public int minInsertions(String s) {
        char[] arr=s.toCharArray();
        int n=arr.length;
        int[][] dp=new int[n][n];

        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(arr[i]==arr[j]) dp[i][j]=dp[i+1][j-1];
                else dp[i][j]=Math.min(dp[i][j-1],dp[i+1][j])+1;
            }
        }

        return dp[0][n-1];
    }
}



//最长递增子序列
class Solution8 {
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];


        int max=0;

        for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }


            }

            max=Math.max(max,dp[i]);
        }

        return max;

    }
}



//环形数组的子数组
class Solution9 {
    public int maxSubarraySumCircular(int[] nums) {
        int sum=0;
        int dp1=0;

        int dp2=0;

        int max=nums[0];
        int min=nums[0];



        for(int x:nums){
            dp1=Math.max(dp1+x,x);
            dp2=Math.min(dp2+x,x);
            sum+=x;

            max=Math.max(max,dp1);
            min=Math.min(min,dp2);

        }


        if(sum==min) return max;

        int ret=sum-min;


        return max>ret?max:ret;

    }
}


//单词拆分
class Solution10 {
    public boolean wordBreak(String s, List<String> wordDict) {

        Set<String> set=new HashSet<>(wordDict);

        int n=s.length();
        boolean[] dp=new boolean[n];

        for(int i=0;i<n;i++){
            if(set.contains(s.substring(0,i+1))){
                dp[i]=true;
                continue;
            }
            for(int j=1;j<=i;j++){
                if(dp[j-1]&&set.contains(s.substring(j,i+1))){
                    dp[i]=true;
                    break;
                }

            }

        }

        return dp[n-1];

    }
}